# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        #         n = len(lists)
        #         if n==0 or not lists[0]:
        #             return None
        #         if n<=1:
        #             return lists[0]
        #         s = self.merge(lists[0],lists[1])

        #         for i in range(2,n):
        #             s = self.merge(s,lists[i])
        #         return s

        #     def merge(self,s1,s2):
        #         if not s1:
        #             return s2
        #         if not s2:
        #             return s1

        #         head = cur=ListNode(0)

        #         while s1 and s2:
        #             if s1.val<s2.val:
        #                 cur.next = s1
        #                 s1 = s1.next
        #             else:
        #                 cur.next = s2
        #                 s2 = s2.next
        #             cur = cur.next
        #         cur.next = s1 or s2
        #         return head.next
        #

        '''
        思路是把链表都加入一个数组中，然后排序，再加到最后的链表中，算法复度为O(nlog(n))
        '''

        res = []
        for i in lists:
            while i:
                res.append(i.val)
                i = i.next
        if res == []:
            return []
        res.sort()
        l = ListNode(0)
        first = l
        while res:
            l.next = ListNode(res.pop(0))
            l = l.next
        return first.next

